package algorithm.sort.n2;

/**
 * @author: Oliver
 * @time: 2020/5/31/13:08
 * 插入排序 时间复杂度为 N^2  最大值排序
 * （近乎有序的数组排序）适用于数组有序性很强的排序，可以提前终止循环条件。
 * 在最优的情况下，也就是说是一个完全有序的数组，插入排序的时间复杂度可以是O（N）
 * 插入排序每次进行该索引位置元素和前一个元素比较  如果当前位置元素>前一个位置元素，进行交换位置，直到满足当前<前一个位置元素，或者到index=0情况终止
 * 插入排序为啥会优于冒泡排序，因为减少了移动的次数，当整体都不需要移动的时候，他就会终止
 */
public class InsertionSort {

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int temp = arr[i];
            //从index =i 的位置向前比较
            int j = i;
            for (; j > 0; j--) {
//                如果遇到他比前一个元素位置小，就终止循环，因为一直在修改数组arr所以这里不能使用arr[j]>arr[j-1]
                if (temp > arr[j - 1]) {
                    //进行记录当前元素 将前一个元素复制给后一个元素
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            //此时j指向需要被替换的元素
            arr[j] = temp;
        }
    }

    //    实现对arr[] [l……r]插入排序
    public static void sortIndex(Comparable[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            Comparable temp = arr[i];
            int j = i;
            //此时j要比比较的左边界大
            for (; j > l; j--) {
                if (temp.compareTo(arr[j - 1]) > 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            //这里j指向待插入元素位置
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {12, 214, 1, 2, 4, 56, 23, 12};
        sortIndex(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }
}
